% Avaliação da ("softwareness") Redes de Software e outros tipos de redes
% complexas (5-10)
%	
%		 * as redes geradas são verossímeis?
%
% deu 7 páginas.

% oops! http://www.statsoft.com/textbook/basic-statistics/
% Are correlation coefficients "additive?" No, they are not. For example, an average of correlation coefficients in a number of samples does not represent an "average correlation" in all those samples. Because the value of the correlation coefficient is not a linear function of the magnitude of the relation between the variables, correlation coefficients cannot simply be averaged. In cases when you need to average correlations, they first have to be converted into additive measures. For example, before averaging, you can square them to obtain coefficients of determination, which are additive (as explained before in this section), or convert them into so-called Fisher z values, which are also additive.
% .. also: http://forum.researchinfo.com/showthread.php?t=1692

\chapter{Avaliação de Modelos de Redes} \label{cap:avaliacao}

\begin{section}{Introdução}
Os três modelos apresentados anteriormente --- BCR+, LFR e CGW --- geram redes organizadas em módulos. Tal condição, no entanto, não é suficiente para que os modelos sejam usados em estudos sobre ferramentas de engenharia reversa. É importante que os modelos gerem redes que se assemelham a redes extraídas de sistemas de software reais.

Daqui para frente, redes que se assemelham a redes de software serão chamadas de \emph{redes software-realistas}. Redes de software são, por definição, software-realistas. Redes estudadas em outros domínios (ex.: redes biológicas) são, por pressuposto, não software-realistas.

O objetivo deste capítulo é avaliar se os modelos são capazes de gerar redes software-realistas. , com uma escolha adequada de valores para os parâmetros,

Para apoiar a avaliação dos modelos, foi desenvolvida uma função que classifica redes em duas categorias: redes software-realistas e redes não software-realistas. Essa função foi então aplicada a redes geradas pelos três modelos. Como resultado, constatou-se que todos os modelos geram tanto redes software-realistas quanto redes não software-realistas. A partir daí foram identificadas regras práticas que permitem prever a categoria de uma rede gerada pelos modelos a partir da análise dos parâmetros usados na geração.

% Este capítulo está divido em quatro seções. Na Seção XXX é apresentada uma função de classificação, C($x$), que define formalmente o conceito de software-realismo. A função classifica uma rede em software-realista ou não software-realista com base apenas na estrutura da rede. 
% 
% Na Seção XXX é relatado um experimento realizado com a finalidade de validar a função de classificação. Dois critérios são avaliados:
% 
% \begin{itemize}
% 	\item a função deve classificar como software-realista as redes que são extraídas a partir de sistemas de software;
% 	\item a função deve classificar como não software-realista as redes que são estudadas fora do domínio de software (ex.: redes biológicas, redes sociais, redes linguísticas).
% \end{itemize}
% 
% O segundo critério faz sentido porque pesquisas anteriores já mostraram que os domínios exemplificados possuem perfis de concentração de tríades distinguíveis entre si. É de se esperar que o mesmo ocorra com o domínio de software em relação aos demais domínios. De fato, o experimento revelou que a função de classificação escolhida atende aos dois critérios.
% 
% Na Seção XXX a função de classificação é aplicada a milhares de redes geradas pelos modelos. Como resultado, constatou-se que todos os modelos geram tanto redes software-realistas quanto redes não software-realistas. Além disso, foram identificadas regras práticas que relacionam, com alta acurácia, valores de parâmetros dos modelos com a classificação da rede resultante.
% 
% A Seção XXX fornece um sumário dos resultados.

\end{section}

\begin{section}{Uma Função de Classificação de Redes}

Classificação é a tarefa de atribuir objetos a categorias pré-definidas CITE_YANG. Nesta seção é proposta e avaliada uma função que classifica redes em duas categorias: redes software-realistas e redes não software-realistas. Dada a subjetividade do conceito de software-realismo, a função de classificação proposta é construída com base em amostras de redes de software (consideradas software-realistas) e redes de outros domínios (consideradas não-software realistas).

A função de classificação deve ser precisa. Em outras palavras, quando aplicada a um conjunto de redes, a maioria das redes classificadas como software-realistas devem de fato ser software-realistas. A precisão da função é estimada com base ...

\begin{section}{Definição}

Dada uma rede $x$, uma função que classifica $x$ segundo seu software-realismo, C($x$), pode ser assim descrita:
	
$$
C(x) ~=~ 
\left\{
\begin{array}{cl}
1 & \mbox{se $x$ é software-realista;} \\
0 & \mbox{caso contrário.}
\end{array}
\right.
$$

Não é possível determinar diretamente se uma rede arbitrária é software-realista, uma vez que o conceito de software-realismo é informal. Por isso, é preciso encontrar uma função computável que forneça uma aproximação razoável da função C($x$) definida informalmente.

Optamos por uma definição que se baseia no aprendizado de exemplos das duas categorias de redes. Seja $R$ um conjunto de redes consideradas software-realistas e $\bar{R}$ um conjunto de redes consideradas não software-realistas. A função proposta, C($x$, $R$, $\bar{R}$), classifica uma rede, $x$, tomando como referência os conjuntos $R$ e $\bar{R}$.

A função C($x$, $R$, $\bar{R}$) é definida a partir das funções $\mathrm{S}(x, R)$ e $\mathrm{S}_0(R, \bar{R})$:

$$
C(x, R, \bar{R}) ~=~ 
\left\{
\begin{array}{cl}
1 & \mbox{se } $\mathrm{S}(x, R) \ge S_0(R, \bar{R})$ \\
0 & \mbox{caso contrário.}
\end{array}
\right.
$$

A função $\mathrm{S}(x, R)$ representa o grau de software-realismo de uma rede. O valor de $S_0(R, \bar{R})$ representa um limiar de software-realismo. Quando o grau de software-realismo da rede $x$ supera o limiar, a rede é classificada como software-realista (valor 1); nos demais casos, a rede é classificada como não software-realista (valor 0).

A definição de $\mathrm{S}(x, R)$ se baseia métrica de similaridade entre redes, sim($x$, $y$), definida no Capítulo XXX como o coeficiente de correlação entre os perfis de concentração de tríades das redes. O valor da função $\mathrm{S}(x, R)$ é definido como a média aritmética dos valores de similaridade entre $x$ e as redes de $R$:

$$
\mathrm{S}(x, R) ~=~ \frac{
\displaystyle\sum_{s \in R} \mathrm{sim}(x, s)
}{|R|} \mathrm{,}
$$


se baseia na métrica de similaridade entre redes definida no Capítulo XXX, sim($x$, $y$), equivalente ao coeficiente de correlação entre os perfis de concentração de tríades das redes. A função pode ser definida da seguinte forma:

$$
C(x, R, \bar{R}) ~=~ 
\left\{
\begin{array}{cl}
1 & \mbox{se }$x$ é software-realista;} \\
0 & \mbox{caso contrário.}
\end{array}
\right.
$$


Uma função que classifica uma dada rede, $x$, em uma das duas categorias, pode ser descrita da seguinte 

Como não se sabe determinar se uma rede é ou não software-realista, é preciso recorrer a uma aproximação

Sejam $R$ um conjunto de redes consideradas software-realistas e $\bar{R}$ um conjunto de redes consideradas não software-realistas. Uma função que classifica uma dada rede, $x$, em uma das duas categorias, pode ser descrita da seguinte forma:

Propomos uma função de classificação
	
\end{section}




A distinção entre as duas categorias não é evidente. Apenas analisando a estrutura de uma rede, é possível identificar uma característica que determine a categoria à qual a rede pertence? Uma possível característica seria a distribuição dos graus dos vértices. Sabe-se que redes de software possuem uma distribuição livre de escala. Tal característica, no entanto, não é suficiente

Abordagem

 Uma função de classificação, neste caso, pode ser definida da seguinte forma:

% método/algoritmo de aprendizagem de máquina

Nesta seção é definido um procedimento para se construir uma função que classifica redes em dois grupos: redes software-realistas e redes não software-realistas. Uma função desse tipo pode ser definida da seguinte forma:

$$
C(x) ~=~ 
\left\{
\begin{array}{cl}
1 & \mbox{se $x$ é software-realista} \\
0 & \mbox{caso contrário,}
\end{array}
\right.
$$

onde $x$ é uma rede. A função C($x$) é chamada de função de classificação, pois classifica qualquer rede como software-realista (valor 1) ou como não software-realista (valor 0). O objetivo da avaliação apresentada neste capítulo é determinar se existe alguma rede $x$ gerada por algum dos modelos tal que C($x$) = 1.

Para auxiliar a definição formal de C($x$), foi desenvolvida a métrica $S$, que representa o quanto uma rede se assemelha a redes de software, em uma escala contínua de 0 a 1. O valor de $S$ para uma rede $x$, S($x$, $R$), é definido como a similaridade média entre a rede $x$ e uma amostra de redes de software, $R$:

$$
\mathrm{S}(x, R) ~=~ \frac{
\displaystyle\sum_{s \in R} \mathrm{sim}(x, s)
}{|R|} \mathrm{,}
$$

onde \emph{sim} corresponde à métrica de similaridade entre redes apresentada no Capítulo XXX, definida como o coeficiente de correlação de Pearson entre os perfis de concentração de tríades das redes.

Uma rede é então classificada como software-realista somente se o valor S é maior ou igual a um valor constante pré-estabelecido, $S_0$, ou limiar de software-realismo:

$$
C(x) ~=~ 
\left\{
\begin{array}{cl}
1 & \mbox{se } $\mathrm{S}(x) \ge S_0$ \\
0 & \mbox{caso contrário.}
\end{array}
\right.
$$

A equação não define completamente a função C($x$). Uma definição completa depende da escolha de um conjunto $R$ de redes de software e de um valor para o limiar $S_0$. A escolha de $S_0$ tem como objetivo aumentar a acurácia da função, isto é, o número de redes corretamente classificadas pela função.

Uma forma de otimizar o valor de $S_0$ é através da coleta de dois conjuntos: $R$, um conjunto de redes de software, e $\bar{R}$, um conjunto de redes de outros domínios. A união dos conjunto $R$ e $\bar{R}$ forma o conjunto $U$, ou universo. Para tanto, é calculado o valor de S($x$) para cada rede, isto é, a similaridade média entre cada de $R \cap \bar{R}$ e as redes de $R$. Então cada valor de S($x$) é considerado como $S_0$ e a acurácia de C($x$) é calculada. O valor de S($x$) com a maior acurácia é escolhido então como o valor de $S_0$.

% Para fixar um valor de $S_0$, consideramos a distribuição dos valores de $S$ das redes da amostra $R$. Seja $\bar{S}$ a média dos valores $S$ das redes de $R$, e $\sigma$ o desvio-padrão dos valores $S$ das redes de $R$. Optamos por definir $S_0$ da seguinte forma:
% 
% $$
% S_0 = \bar{S} - 3 \sigma
% $$
% 
% A definição de $S_0$ é arbitrária. A inspiração para a nossa definição vem da regra dos três sigmas, da estatística: se os valores seguem uma distribuição normal, $99,7\%$ dos valores estão a menos de três desvios-padrões ($\sigma$) do valor médio $\bar{S}$. Note que não há garantias de que o valor $S$ segue uma distribuição normal. Por isso, a regra dos três sigmas foi usada apenas como inspiração para uma definição arbitrária.
\end{section}

\begin{section}{Avaliação da Função de Classificação}

%	enunciar hipóteses e critérios de sucesso.
%	delineamento experimental: coleta, extração, medição, análise
% ---
% acurácia de teste: 0.973846153846154
% função aprovada:
%   limiar: 0.809316572577955
%   acurácia: 0.984732824427481
%   precisão: 0.970149253731343
%   recall: 1.0
%   f_measure: 0.984848484848485
% ---
% java -cp weka.jar weka.classifiers.rules.OneR -B 6 -v -t lf2.csv
% ten-fold stratified cross-validation


Na seção anterior foi apresentado o arcabouço de uma função que classifica redes em software-realistas ou não software-realistas. Nesta seção a função é instanciada a partir da coleta de redes de software (conjunto $R$) e de redes de outros domínios (conjunto $\bar{R}$). A função é então avaliada segundo dois critérios. Primeiro, a função deve classificar redes de software como software-realistas. Segundo, a função deve classificar como não software-realistas redes encontradas em outros domínios.

Foi desenvolvido um experimento em 4 fases. Primeiramente, foram coletados mais de 60 sistemas de software escritos na linguagem Java e mais de 60 redes estudadas em domínios diversos (conjunto $\bar{R}$). A seguir, foi extraída a rede de dependências entre as entidades de implementação de cada sistema de software coletado, as quais constituem o conjunto de redes de software (conjunto $R$). A partir daí o classificador foi avaliado através de validação cruzada estratificada. Determinou-se que o classificador constrói funções capazes de determinar com alta acurácia a classe de redes analisadas (software-realista ou não-software realista). A partir daí, a função foi instanciada com o conjunto $U$ completo.

\begin{subsection}{Coleta de Redes e Sistemas}
	
	Foram coletadas 66 redes de domínios tão diversos quanto a biologia, a sociologia, a tecnologia e a linguística, com tamanho variando entre 32 e 18.163 vértices. As redes foram obtidas em \emph{websites} de pesquisadores renomados da área de redes complexas. Apenas redes orientadas foram selecionadas para o estudo, uma vez que as redes de dependências entre entidades de software são redes orientadas. A lista completa de redes pode ser encontrada Apêndice \ref{cap:lista-redes}.
	% ...

  Foram coletados 65 sistemas de software escritos em Java, contendo entre 111 e 35.563 classes cada um. Quase todos os sistemas foram selecionados a partir da lista dos sistemas mais populares do repositório SourceForge.net; além destes, foi selecionado o sistema OurGrid, desenvolvido na Universidade Federal de Campina Grande. 

	No caso dos sistemas do SourceForge.net, foram selecionados apenas sistemas distribuídos como um conjunto de arquivos no formato JAR (Java Archive), que contêm código-objeto de cada classe do sistema. Essa restrição foi necessária para simplificar a extração de dependências.

	A linguagem Java foi escolhida por ser uma linguagem de programação popular na qual muitos sistemas de software de código aberto já foram escritos. Além disso, há diversas ferramentas para extrair dependências de programas escritos em Java.

\end{subsection}

\begin{subsection}{Extração de Redes de Software}

	Como os sistemas de software foram coletados sob a forma de código-objeto, foi necessário extrair de cada um deles a sua rede de dependências, ou rede de software. A extração foi realizada através da ferramenta gratuita Dependency Finder\url{http://depfind.sf.net/}, que extrai dependências a partir de código-objeto Java. A escolha se deveu à facilidade de uso via linha de comando e à sua robustez.
	
	Na extração das redes, classes e interfaces foram consideradas como entidades. Como dependências entre classes/interfaces, foram consideradas todas as referências de uma classe/interface no código de outra classe/interface, incluindo relacionamentos de herança, chamadas de método, instanciação, leitura ou escrita de atributos e agregação.

	A lista completa dos sistemas de software pode ser encontrada no Apêndice \ref{cap:lista-redes}, juntamente com o número de vértices e arestas de cada rede de dependências correspondente.

\end{subsection}

\begin{subsection}{Classificação das Redes Coletadas}
	
	% Classificar redes de outros domínios primeiro, e então classificar redes de software. Explicar que no segundo caso é mais complicado (threefold ou 5-fold cross-validation -- repetidos 10 vezes), uma vez que temos que dividir entre conjunto de treinamento e conjunto de validação. 
	
	% conjunto de treinamento vs. conjunto de validação (2/3 vs. 1/3)
	
	% a seguir, os conjuntos são misturados para gerar o classificador final.
	
	% conjunto de teste: as redes sintéticas! (ou seria o contrário, conjunto de validação?)
	
	% a acurácia de X% é relevante? Quanto conseguiríamos se "chutássemos"? (ver Bernoulli, p. 149 do livro de Data Mining da Univ. do Weka)
	

\end{subsection}


% Já se sabe que os três modelos geram redes que, a exemplo de redes de software, são livres de escala. Isoladamente, no entanto, esta propriedade não é suficiente para avaliar os modelos, uma vez que muitas redes livres de escala conhecidas não são redes do software (por exemplo, redes biológicas). Partindo da hipótese de que redes de outros domínios são estruturalmente diferentes de redes de software, o critério usado para avaliar se as redes sintéticas são software-realistas deve ser robusto o suficiente para determinar que redes de outros domínios não são software-realistas.
% 
% Neste capítulo é descrito um experimento no qual se verificou que os três modelos são capazes de gerar redes software-realistas. A partir dessa conclusão, foi encontrado um subconjunto de valores para os parâmetros dos modelos que garantem, com alta taxa de acerto, que as redes geradas serão software-realistas.
% 
% A ideia básica do experimento é gerar redes usando diversos valores para os parâmetros dos modelos e então medir a similaridade entre as redes sintéticas e um conjunto de redes de software extraídas de sistemas reais e de redes de outros domínios. Para apoiar a realização do experimento, foram coletadas 131 redes:
% ...

\begin{itemize}
	\item redes de software: foram coletados 65 sistemas de software escritos em Java, contendo entre 111 e 35.563 classes cada um. A linguagem Java foi escolhida por ser uma linguagem de programação popular na qual muitos sistemas de software de código aberto já foram escritos. A maior parte dos sistemas foram selecionados a partir da lista dos sistemas mais populares do repositório SourceForge.net; além desses, foram selecionados sistemas com os quais o autor tem familiaridade, como o OurGrid. Para extrair a rede de dependências dos sistemas foi usada a ferramenta Dependency Finder, disponível em \url{http://depfind.sf.net/}, que foi escolhida pela robustez e pela facilidade de uso.
	\item redes de outros domínios: foram coletadas 66 redes de domínios tão diversos quanto a biologia, a sociologia, a tecnologia e a linguística, com tamanho variando entre 32 e 18.163 vértices.
\end{itemize}

Todas as redes usadas no estudo estão listadas no Apêndice \ref{cap:lista-redes}.

\end{section}

\begin{section}{Software-Realismo de uma Rede} \label{sec:realismo-rede}

Para apoiar o experimento, foi desenvolvido um modelo de classificação que classifica redes em dois grupos: software-realistas e não software-realistas. O modelo de classificação é baseado em uma métrica de similaridade entre duas redes. Para determinar a classificação de uma rede, é medida a similaridade da rede em relação a todas as 65 redes de software da amostra. A rede é considerada software-realista quando a média das similaridades é superior a um limiar pré-determinado.

A partir da métrica de similaridade entre redes baseada em perfis de concentração de tríades (PCT), apresentada no Capítulo \ref{cap:redes}, foi desenvolvida a métrica S, que representa o quanto uma rede se assemelha a redes de software. O valor de S para uma rede $x$, S($x$), é definido como a similaridade média entre a rede $x$ e uma amostra de redes de software, $R$:

$$
\mathrm{S}(x) ~=~ \frac{
\displaystyle\sum_{s \in R} \mathrm{sim}(x, s)
}{|R|} \mathrm{,}
$$

Neste estudo, consideramos que $R$ é a amostra de 65 redes de software.

Para os propósitos desta pesquisa, a métrica S deve satisfazer duas condições: (i) ela deve ter valores altos quando aplicada a redes de software; (ii) ela deve ter valores mais baixos quando aplicadas a redes de outros domínios. Com a finalidade de avaliar se a métrica satisfaz as condições, foi computada métrica S de cada uma das 131 redes selecionadas para este estudo. Para a extração dos PCTs, foi usada a ferramenta igraph \cite{igraph}.

O valor de S para as redes de software oscilou entre 0,83 e 0,98, com média igual a 0,97 e desvio-padrão igual a 0,03. O alto valor médio de S e o baixo desvio-padrão mostram que a métrica caracteriza adequadamente as redes de software, capturando seus padrões estruturais.

Um total de 97,0\% das redes de outros domínios recebeu um valor de S inferior a 0,83. Algumas redes receberam valores negativos de S, revelando uma alta dissimilaridade com redes de software. Apenas duas redes receberam valores altos de S: a rede de links entre blogs sobre política (S = 0,97) e a rede neural do verme C. Elegans (S = 0,88). Investigações futuras serão necessárias para descobrir as razões por trás dos valores altos e métricas auxiliares que possam diferenciar as duas redes de redes de software.

A partir da métrica S é definido um modelo de classificação de redes: redes com valor S superiores a um determinado limiar são classificadas como redes software-realistas; as demais redes são classificadas como não software-realistas.

Como existem redes de outros domínios com valor de S alto, é impossível construir um modelo de classificação perfeito, independentemente da escolha do limiar. Um modelo de classificação pode, no entanto, ser avaliado em termos de sua acurácia, de sua precisão e de sua cobertura. 

Considere o universo de 131 redes (65 redes de software e 66 de outros domínios) coletadas para este estudo. Seja $R$ o conjunto de 65 redes de software e $L$ o subconjunto das 131 redes que são classificadas como software-realistas. Seja $\bar{X}$ o complemento do conjunto $X$ (por exemplo, $\bar{R}$ é o conjunto de 66 redes de domínios diversos). A precisão do modelo é

$$
\mbox{precisão:} ~\frac{|R \cap L|}{|L|},
$$

e a cobertura é

$$
\mbox{cobertura:} ~\frac{|R \cap L|}{|R|}
$$

e a acurácia é

$$
\mbox{acurácia:} ~\frac{|R \cap L| + |\bar{R} \cap \bar{L}|}{|R \cup \bar{R}|}.
$$


Aumentar o limiar tem o efeito de reduzir a cobertura, pelo fato de menos redes de software serem classificadas como software-realistas. Reduzir o limiar tem o efeito de reduzir a precisão, pelo fato de mais redes de outros domínios serem classificadas como software-realistas.

A escolha de um limiar adequado, portanto, depende da importância dada à precisão e à cobertura. Como o objetivo do experimento é avaliar se redes sintéticas são software-realistas, é mais importante ter alta precisão, pois isso representa um teste mais forte.

Para obter 100\% de precisão, o limiar deve ser 0,98, um valor que está acima do maior valor de S para redes de outros domínios. A cobertura, neste caso, seria de apenas 44,6\%, pois muitas redes de software seriam incorretamente classificadas. Foi escolhido o valor 0,88 para o limiar, que é suficiente para classificar a rede do verme C. Elegans como não software-realista e render valores altos para a cobertura (95,4\%) e para a precisão (96,9\%).

\end{section}

\begin{section}{Avaliação Empírica do Software-Realismo de Modelos de Redes}

Na seção anterior foi mostrado que muitas redes livres de escala de diversos domínios podem ser diferenciadas de redes de software através de um modelo de classificação simples baseado em perfis de concentração de tríades (PCTs). Nesta seção é descrito um experimento que mostra que os três modelos de redes organizadas em módulos geram redes software-realistas. O experimento consiste em gerar redes usando diversas combinações de parâmetros dos três modelos, e então classificar cada rede como software-realista ou não software-realista. O número de vértices foi fixado em 1.000 e os valores dos demais parâmetros foram variados em passos discretos. 

%No total, foram geradas 9.500 redes com o modelo BCR+, 38.790 redes com o modelo CGW e 1.296 redes com o modelo LFR.

\begin{subsection}{Seleção de Parâmetros} \label{sec:parametros}

Para o modelo BCR+, foram escolhidos grafos de módulos extraídos a partir de dependências entre arquivos JAR de 5 sistemas de software: GEF (2 módulos), iBATIS (4 módulos), MegaMek (8 módulos), findbugs (16 módulos) e zk (32 módulos). Como muitos dos arquivos JAR foram concebidos para serem reusados em projetos distintos, eles são uma boa aproximação do conceito de módulo. Para os demais parâmetros, os seguintes valores foram escolhidos:

\begin{itemize}
	\item $p_1, p_2, p_3 \in \{0,0; 0,2; 0,4; 0,6; 0,8; 1,0\}$, com $p_1 + p_2 + p_3 = 1$ e $p_1 + p_2 > 0$ (do contrário a rede jamais alcançaria 1.000 vértices);
	\item $\delta_{in}, \delta_{out} \in \{0, 1, 2, 3, 4\}$;
	\item $\mu \in \{0,0; 0,2; 0,4; 0,6\}$ (valores altos foram evitados a fim de ignorar redes com módulos fortemente acoplados).
\end{itemize}

Combinando-se todas as possíveis atribuições de valores a parâmetros dentro dos domínios escolhidos chega-se a 9.500 configurações possíveis.
%Com essa escolha, há um total de 9.500 combinações de valores de parâmetros.
%Para cobrir todas as combinações de valores de parâmetros, foram geradas 9.500 redes com o modelo BCR+.

Para o modelo CGW, os seguintes valores de parâmetros foram escolhidos:

\begin{itemize}
	\item $p_1, p_2, p_3, p_4 \in \{0,0; 0,2; 0,4; 0,6; 0,8; 1,0\}$, com $p_1 + p_2 + p_3 + p_4 = 1$ e $p_1 > 0$ (do contrário a rede jamais alcançaria 1.000 vértices);
	\item $e_1, e_2, e_3, e_4 \in \{1, 2, 4, 8\}$ (com a restrição de que $e_i$ não varia quando $p_i = 0$, o que não faria sentido);
	\item $\alpha \in \{-1, 0, 1, 10, 100, 1000\}$
	\item $m \in \{2, 4, 8, 16, 32\}$.
\end{itemize}

O total de combinações, neste caso, é 38.790. O número elevado se deve à grande quantidade de parâmetros a serem combinados.

Além disso, considerou-se que a rede inicial é formada por dois vértices contidos em um mesmo módulo, juntamente com uma aresta bidirecional que liga os vértices.

No caso do modelo LFR, os seguintes valores foram escolhidos para os parâmetros:

\begin{itemize}
	\item parâmetro de mistura: $\mu \in \{0,0; 0,2; 0,4; 0,6\}$;
	\item expoente da distribuição de graus: $\gamma \in \{2,18; 2,70; 3,35\}$;
	\item expoente da distribuição de tamanhos de módulos: $\beta \in \{0,76; 0,99; 1,58\}$;
	\item grau médio: $k \in \{5, 10, 15, 25\}$;
	\item grau máximo: $max_k \in \{58, 157, 482\}$;
	\item tamanho do menor módulo: $min_m \in \{1, 10, 273\}$.
\end{itemize}

O total de combinações, neste caso, é 1.296.

Para chegar aos valores para os parâmetros do modelo LFR, foram analisadas métricas de redes de software com cerca de 500 a 2.000 classes. Para cada métrica foram identificados os valores mínimo, mediano e máximo; esses foram os valores usados nos parâmetros correspondentes.

%Para cobrir todas as combinações de valores de parâmetros, foram geradas 1.296 redes com o modelo LFR.

\end{subsection}

\begin{section}{Geração de Redes}
	Foi gerada uma rede para cada combinação de valores para os parâmetros de cada modelo.
\end{section}

\begin{subsection}{Resultados}

Usando o modelo de classificação descrito na Seção \ref{sec:realismo-rede}, cada rede sintética foi classificada como software-realista ou não software-realista. Os resultados estão condensados na Tabela \ref{tab:results}.

\begin{table}
\caption{Resultados da classificação de redes sintéticas}
\centering
\begin{tabular}{|l|l|}
\hline
Modelo & Redes classificadas \\ & como software-realistas \\
\hline 
\hline
BCR+ & 21.18\% \\ % 2012 / 9500
\hline
CGW  & 19.40\% \\  % 7524 / 38790
\hline
LFR  & 31.25\% \\ %  405 / 1296
\hline
\end{tabular}
\label{tab:results}
\end{table}

Todos os modelos geraram redes software-realistas e redes não software-realistas. A proporção de redes software-realistas foi maior que 19\% em todos os casos, descartando a possibilidade de que esse resultado tenha sido obtido por acaso. (A proporção exata para cada modelo não deve ser não deve ser interpretada como medida de qualidade, pois com esses resultados não é possível determinar se um modelo é melhor do que os outros.)
% Para afirmar isso seria necessário repetir o experimento com redes de Erdos-Renyi

Naturalmente, esse resultado tem pouco valor prático se não for estabelecida uma relação entre os valores dos parâmetros usados na geração de uma rede e a classificação da rede. Na prática é importante saber quais valores de parâmetros tendem a gerar redes software-realistas.

Para ajudar a descobrir essa relação, foi utilizado o algoritmo 1R \cite{OneR} da mineração de dados. O algoritmo analisa, para cada rede, os parâmetros usados na sua geração e a sua classificação, e então encontra uma regra que relaciona o valor de um único parâmetro com a classificação da rede. Regras encontradas pelo 1R podem ser avaliadas de acordo com a sua acurácia, isto é, a proporção de redes corretamente classificadas.

As regras encontradas pelo algoritmo 1R são exibidas na Tabela \ref{tab:rules}. As regras são bastante simples e, portanto, fáceis de seguir. (Essa característica do 1R foi o que motivou a sua escolha em detrimento de outros algoritmos de mineração de dados.) Apesar da simplicidade, as regras encontradas possuem uma acurácia de cerca de 80\% para todos os modelos.

% regra obtida a partir dos conjuntos completos
% acurácia, precisão e cobertura obtidos a partir de 10-fold stratified cross-validation
% --
% BCR+
%  regra: p1 >= 0.5
%  acurácia: 83.7904%
%  TP: 5947, FP: 1006, FN: 525, TN: 1967
%  precisão: 85.5314252840501%
%  cobertura: 91.8881334981459%
% --
% CGW
%  regra: e3 >= 3
%  acurácia: 76.623%
%  TP: 11278, FP: 3780, FN: 5287, TN: 18441
%  precisão: 74.8970646832249%
%  cobertura: 68.0833081798974%
% --
% LFR
%  regra: expdegree >= 3.025
%  acurácia: 78.3763
%  TP: 579, FP: 277, FN: 0, TN: 425
%  precisão: 67.6401869158878%
%  cobertura: 100%

\begin{table}
\caption{Regras para prever a classificação de uma rede sintética.}
\centering
\begin{tabular}{|l|l|l|}
\hline
Modelo & Regra & Acurácia & Precisão & Cobertura \\
\hline 
\hline
\multirow{2}{*}{BCR+}
     & $p_1 \ge 0.5 \Rightarrow \mbox{rede software-realista}$ & \multirow{2}{*}{82.4\%} & \multirow{2}{*}{82.4\%} & \multirow{2}{*}{82.4\%} \\ 
     & $p_1 < 0.5 \Rightarrow \mbox{rede não software-realista}$ & \\ 
\hline
\multirow{2}{*}{CGW}
     & $p_1 \ge 0.5 \Rightarrow \mbox{rede software-realista}$ & \multirow{2}{*}{82.3\%} \\  
     & $p_1 < 0.5 \Rightarrow \mbox{rede não software-realista}$ & \\  
\hline
\multirow{2}{*}{LFR}   
     & $\gamma < 2.44 \Rightarrow \mbox{rede software-realista}$ & \multirow{2}{*}{78.9\%} \\ 
     & $\gamma \ge 2.44 \Rightarrow \mbox{rede não software-realista}$ & \\ 
\hline
\end{tabular}
\label{tab:rules}
\end{table}

\end{subsection}

\end{section}

\begin{section}{Conclusão}
	
	Os modelos CGW, LFR e BCR+ podem gerar, a depender dos valores atribuídos a seus parâmetros, redes software-realistas, isto é, redes que se assemelham a redes de dependências estáticas extraídas de programas escritos em Java. Esse resultado foi obtido em um experimento no qual as redes geradas pelos modelos foram comparadas a redes extraídas de 65 sistemas de software escritos em Java. Ademais, foram identificadas regras práticas capazes de prever, com 80\% de acurácia, se uma atribuição de valores a parâmetros de um modelo resulta em uma rede software-realista.
	
	 A comparação entre redes foi realizada através da métrica de similaridade que se baseia no perfil de concentração de tríades (PCT) das redes. A métrica de similaridade foi, antes, validada com um conjunto de 66 redes que não pertencem ao domínio de software. A métrica se mostrou adequada para diferenciar essas redes de redes de software com mais de 95\% de cobertura e precisão.
	
\end{section}
 
% Descrição do experimento segundo o arcabouço de Basili.
% 
% Descrição geral do experimento: similaridade entre redes sintéticas e redes de software usando tríades.
% 
% PARTE 1
% 
% Similaridade entre duas redes.
% 
% Conjuntos de dados.
% 
% Métrica de softwareness e avaliação através de precisão e cobertura.
% 
% PARTE 2
% 
% Avaliação dos modelos
% 
% Escolha dos parâmetros
% 
% Resultados